Toss strange coins

Time: O(N^2); Space: O(N); medium

You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.

Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.

Example 1:

Input: prob = [0.4], target = 1

Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0

Output: 0.03125

Constraints:

  • 1 <= len(prob) <= 1000

  • 0 <= prob[i] <= 1

  • 0 <= target <= len(prob)

  • Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Hints:

  1. dp[i][j] := prob of j coins face up after tossing first i coins.

  2. dp[i][j] = dp[i-1][j] * (1 – p[i]) + dp[i-1][j-1] * p[i]

1. Dynamic programming [O(N^2), O(N)]

[6]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def probabilityOfHeads(self, prob, target):
        """
        :type prob: List[float]
        :type target: int
        :rtype: float
        """
        dp = [0.0]*(target+1)
        dp[0] = 1.0

        for p in prob:
            for i in reversed(range(target+1)):
                dp[i] = (dp[i-1] if i >= 1 else 0.0)*p + dp[i]*(1-p)

        return dp[target]

[7]:

s = Solution1()

prob = [0.4]
target = 1
assert s.probabilityOfHeads(prob, target) == 0.40000

prob = [0.5,0.5,0.5,0.5,0.5]
target = 0
assert s.probabilityOfHeads(prob, target) == 0.03125